package com.leetcodehot.problems;

import java.util.ArrayList;
import java.util.List;

public class problems2476 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 做法一，会超时，分析一下超时的原因在于，每一次查询新的target都需要从头开始再跑一次递归
     * 所以，我们采用做法二，如果可以加快每一轮查询target的速度，那么整体上来看是更快的。
     * 考虑到题意非常类似有序数组二分查找，我们使用中序遍历构建有序数组，然后每轮对target进行查询
     */
    /*
    private int target;

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        int n = queries.size();
        List<List<Integer>> answers = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            int val = queries.get(i);
            List<Integer> integers = new ArrayList<>();
            target = val;
            integers.add(dfs1(root));
            integers.add(dfs2(root));
            answers.add(integers);
        }
        return answers;
    }
    private Integer dfs1(TreeNode root) {
        if (root == null) return -1;
        if (root.val == target) return root.val;
        else if (root.val < target) {
            int right = dfs1(root.right);
            return right == -1 ? root.val : right;
        } else {
            return dfs1(root.left);
        }
    }
    private Integer dfs2(TreeNode root) {
        if (root == null) return -1;
        if (root.val == target) return root.val;
        else if (root.val > target) {
            int right = dfs2(root.left);
            return right == -1 ? root.val : right;
        } else {
            return dfs2(root.right);
        }
    }
    */

    /**
     * 做法二，先构建有序数组，再二分
     */
    private List<Integer> orderList = new ArrayList<>();

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        dfs(root);
        List<List<Integer>> answers = new ArrayList<List<Integer>>(queries.size());
        Integer[] orderNums = orderList.toArray(new Integer[0]);
        int left = -1, right = orderNums.length;
        for (int target : queries) {
            List<Integer> integers = new ArrayList<>();
            left = -1;
            right = orderNums.length;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (orderNums[mid] <= target) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            integers.add(left == -1 ? -1 : orderNums[left]);
            left = -1;
            right = orderNums.length;

            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (orderNums[mid] >= target) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            integers.add(right == orderNums.length ? -1 : orderNums[right]);
            answers.add(integers);
        }
        return answers;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        orderList.add(root.val);
        dfs(root.right);
    }
}
